Digital signatures can be formed using asymmetric key cryptography. Asymmetric key cryptography involves the use of certain mathematical constructs considered to be difficult to reverse, e.g. factorization of large integers or computing discrete logarithms of large integers. These mathematical constructs are used to generate a pair of cryptographic keys, with the property that data encrypted by one key can only be decrypted by the other key. One key is kept secret by the owner, and is referred to as the private key; the other key is published to the world, and is referred to as the public key.
Given the algorithmic nature of the mathematical constructs used to generate a given key pair, it is always possible to find the corresponding private key for a known public key given sufficient time and computing resources. To combat this problem each public key is assigned a finite period of time over which the key can be considered valid. This time period reflects an estimate of the amount of time required to determine the private key for a given public key, given the current state of the art in computing and cryptanalysis. Because it is always possible for the private key to be inadvertently compromised, there must also exist a means for notifying users of the corresponding public key that the key is no longer valid.
To facilitate the assignment of validity periods to public keys, and to support the notification of users when a public key becomes unexpectedly invalid, the concepts of digital certificates and certificate revocation lists (CRLs) have been introduced. Digital certificates are distributed by an issuer to their owners and are data structures which have a standardized format, such as that specified in the ITU X.509 standard, among others. FIG. 1 shows a conceptual version of a digital certificate 100.
A digital certificate typically contains a serial number 102, information identifying the issuer of the certificate 104, information identifying the owner of the certificate 106, the owner's public key issued by the issuer 108 and information about the validity period 110 of the digital certificate. The digital certificate is digitally signed 112 with the issuer's private key.
Issuers of digital certificates are referred to as Certificate Authorities (CAs). The CA accepts enrollment requests from users and produces the necessary certificates. In issuing a certificate, the CA attests to the correctness of the certificate it issues by signing each certificate with its own private key. The CA publishes its public key in a certificate as well, in order for users to be able to validate the certificates it issues.
The CA also provides the means for notifying users when the certificates it issues become invalid (i.e., when the user to whom the certificate was issued loses control of the corresponding private key because it was stolen or otherwise compromised.) When a CA is informed that a certificate can no longer be trusted for some reason, the CA revokes the certificate by placing it on a Certificate Revocation List (CRL), which is another standardized data structure specified, for example, by the aforementioned X.509 standard. As conceptually illustrated in FIG. 2, a CRL 120 contains the serial number 122 of each revoked certificate and the date and time 124 at which the CRL was issued. The CRL is also signed by the issuing CA using its digital signature 126, and published in accordance with that CA's security policy, which may call for periodic updates, updates upon request and updates upon the occurrence of pre-defined events, among others.
Often a CA is a member of a hierarchy of CAs, with higher-level CAs attesting to the validity of lower-level CAs. When a CA is part of a hierarchy of CAs, the certificate issued to a lower-level CA is signed by a CA higher in the hierarchy. Since at the highest level of the CA hierarchy there is no higher-level CA available to sign that CAs certificate, the highest-level CA signs its own certificate. The validity of these self-signed certificates is determined through some out-of-band means.
FIG. 3 illustrates a sample hierarchy 200 of certification authorities having a total of N=4 levels of certification authorities with end users being found at more than one level. The highest, or first level certification authority is designated the “root” level and indicated by CA-Root 202. As seen in the hierarchy of FIG. 3, the root CA 202 signs its own root certificate CA-Root 203, puts out a root certificate revocation list CRL-Root 204 in accordance with its security policy, and issues digital certificates DC-1 206 and DC-2, to second level (level-2) certification authorities CA-1 210 and CA-2 212, respectively. The level-2 certification authorities CA-1 and CA-2 put their own certificate revocation lists CRL-1 214 and CRL-2 216, respectively. CA-1 210 also issues digital certificate DC-1 218 to USER-1 220, while CA-2 212 issues digital certificate DC-3 222 to level-3 certification authority CA-3 224. CA-3 puts out CRL-3 226 in accordance with its security policy and also issues digital certificate DC-32 228 to USER-2 230. As seen with CA-1, it is possible for a certification authority to issue digital certificates to both users and to other certification authorities.
The structure of the hierarchy below CA-2 212 should now be clear from the foregoing description of the corresponding structure below CA-1 210. It is noted, however, that two certification authorities can issue different digital certificates to a single user, as seen with the level-4 certification authorities CA-6 232 and CA-7 234, which issue DC-65 236 and DC-75 238 to USER-5 240. Similarly, two certification authorities can issue unique digital certificates to the same certification authority. In such instances where two such digital certificates are received, the owner must keep track of which certificate to use at any given time.
As seen in FIG. 3, USER-1 220 is issued digital certificate DC-11 from the 2nd level certification authority CA-1, and USER-2 is issued digital certificate DC-32 from the 3rd level certification authority CA-3. DC-1 and DC-3 belong to the same certificate chain—the chain comprising DC-3, DC-1 and DC-Root. Within this chain, digital certificate DC-11 belongs to a certificate chain comprising only DC-1 and DC-Root., while digital certificate DC-32 belongs to a certificate chain comprising all three of DC-3, DC-1 and DC-Root. As also seen in FIG. 3, DC-2 belongs to a number of certificate chains, such as the chain comprising DC-6 issued to CA-6 232, DC-4 issued to CA-4, DC-2 issued to CA-2 212 and DC-Root, and the chain comprising DC-7 issued to CA-7 234, DC-5 issued to CA-5, DC-2 and DC-Root.
It should be understood that the hierarchy of the various entities (i.e., certification authorities and users) may be independent of the physical location of the entities, the type of communication links (wireless, wireline, optic, etc.) between the entities, the types of devices (computers, hand-held communication devices, set-top boxes, etc.) and the roles played by the various CAs and users (supplier, consumer, broker, internet service provider, etc.).
Thus, as shown in FIG. 4, the various entities may belong to a common organization, housed at a single site or even a single building 250 and connected via a LAN 252. It is understood that such a LAN may also have storage devices 254, communication devices 256, output devices 258, among others, associated therewith. In such case, a central administrative authority can keep track of all the digital certificates and CRLs, perhaps storing them in a database not accessible by all the entities on the LAN. It should be kept in mind that each entity is not necessarily a distinct computing platform but rather is a process running on that platform. Thus, in the embodiment of FIG. 4, it is entirely possible that all of the CAs and ‘users’ are all implemented as processes running on a single computer, albeit with different trust boundaries amongst the entities and different access privileges accorded to each.
Alternatively, as shown in FIG. 5, the various entities of FIG. 3 may be distributed among various organizations and connected via the internet in any number of different ways. Thus, USER-2, CA-Root, CA-1 and CA-2 are directly connected to the internet, CA-1 also being an internet service provider ISP-1 300. The remaining entities are connected either by internet service providers ISP-2 302 or ISP-3 304 or via a gateway computer 306 to which a LAN or WAN 308 is connected.
It should be noted that the various entities may be connected to one another in any number of ways between the extremes shown in FIGS. 4 and 5. What is important is that a hierarchical system of CAs does not dictate either the location, ownership or role (apart from security) of the various entities.
Once a certificate has been issued to an end user, it can be used to sign digital records which, in this context, includes any and all forms of electronic documents, transactions, files, etc. A record is signed by encrypting some representation of the record with the user's private key. The signature can later be validated by decrypting the representation using the public key contained in the user's certificate and comparing it to the record. However, validating a signature also requires that the certificate containing the public key be verified as well. Checking the encrypted record representation can only verify whether the record matches the signature value; the status of the key used to form the encryption must also be verified.
Checking the validity of a certificate involves a number of steps. The validity period of the certificate must be checked against the current time, to be sure the key contained in the certificate has not expired. The signature applied to the certificate by the issuing CA must be validated, to ensure the certificate contents have not been tampered with. The current CRL for the issuing CA must be checked to determine if the certificate has been revoked. Because the CRL is itself a signed data item, the signature on the CRL must also be checked for validity. Finally, the certificates of the issuing CA and all higher-level CAs must be checked for validity, until the root self-signed certificate is reached. CA certificates are checked in the same manner as the actual end user certificate, by examining validity periods and CRLs for the corresponding higher-level CAs.
Once any element of the digital signature process is no longer valid, any signature based on that element can no longer be considered valid. For example, if the public key in a CA's certificate reaches the end of its validity period, all certificates issued by that CA with that certificate can no longer be validated. Hence, any signatures formed using those certificates can also no longer be validated. Since digital certificates only have a finite period of validity, typically on the order of one year, expiry is a concern. Likewise, if a CA's certificate is ever revoked, all certificates issued by the CA using that certificate are no longer valid, and hence signatures formed using them cannot be successfully validated.
The use of digital signature technologies has begun to permeate almost every sector of society as paper-based functions are moved into electronic form. Digital signatures provide both the capability to identify the signer of an electronic record, and provide the means for protecting the record against tampering. The combination of these two capabilities allows digital signatures to essentially replace paper records and hand-written signatures.
While digital signatures can be used to replace the identity and integrity functions of hand-written signatures and paper records, there are other important characteristics of paper records that digital signatures by themselves cannot replicate.
Principal among these characteristics is the inherent stability of hand-signed paper records, as compared to digitally signed electronic records. That is, a hand-signed paper record remains valid as long as the physical instance of that record exists. Given proper physical safeguards, a paper record can remain valid for extended periods of time.
The validity of digitally signed electronic records, however, is subject to the limitations of the cryptographic primitives in use. For instance, as advances in computing technology provide greater computing power for lower cost, it becomes increasingly easy to dispute the validity of a digital signature based on the computational feasibility of reversing some mathematical construct. Likewise, as advances in cryptanalysis enable new attacks on various encryption algorithms, signatures based on those encryption algorithms will increasingly come under attack.
Thus, to truly duplicate the features and characteristics of hand-signed paper records in the digital age, some means for ensuring the perpetual validity of digital signatures is required.